class Solution {
public:
    class Trie{
    public:
        unordered_map<char,Trie*> next;
        bool isEnd;
        Trie() : isEnd(false){
        }
        
    void insert(Trie* root,string s){
        Trie* node = root;
        for(char e : s){
            if(!node->next.count(e)){
                node->next[e] = new Trie();
            }
            node = node->next[e];
        }
        node->isEnd = true;
    }
    Trie* serach(Trie* root,string s){
        Trie* node = root;
        for(char e : s){
            if(!node->next.count(e)){
                return NULL;
            }
            node = node->next[e];
        }
        return node;
    }
    };
        
    vector<string> res;
    void traceback(Trie* root,string ans,string s,int cur){
     //   cout<<ans<<endl;
        if(cur >= s.size()){
            res.push_back(ans);
            return;
        }
        if(ans != ""){
            ans += " ";
        }
        for(int i = cur;i < s.size();i++){
            string ss = s.substr(cur,i - cur + 1);
            Trie* node = root->serach(root,ss);
            if(node && node->isEnd == true){
                traceback(root,ans + ss,s,i+1);
            }
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        string ans = ""; 
        Trie* root = new Trie();
        for(string& e : wordDict){
            root->insert(root,e);
        }
        
        traceback(root,ans,s,0);
        return res;
    }
};
